package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
 **/
public class No056 {

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：39.5 MB, 在所有 Java 提交中击败了97.87%的用户
     */
    public int[] singleNumbers(int[] nums) {
        // 最终那两个数的异或值
        int n = 0;
        for (int num : nums) {
            n ^= num;
        }

        int m = 1;
        while ((n & m) == 0) {
            m <<= 1;
        }

        // x,y为最终结果值
        int x = 0, y = 0;
        for (int num : nums) {
            if ((num & m) == 0) x ^= num;
            else y ^= num;
        }

        return new int[]{x, y};
    }
}
